{
  // 创建节点类，单独使用
  class Node {
    constructor(element) {
      this.element = element; // 存放当前节点元素数据
      this.next = null; // 创建时将所有节点【后继】都指向为空
    }
  }
  // 用JS语言手动模拟实现链表结构及方法
  class LinkedList {
    constructor() {
      this.head = new Node('head'); // 创建一个链表的头部，且只有一个
    }
    // 查找链表中前驱
    findPreivious(item) {
      let currNode = this.head; // 记录当前节点位置，默认在头部处
      // 当前节点不等于null(尾节点)，节点后继不等于你找的节点时循环
      // 循环中就是多向下移了一针，所以找的是前驱位置
      while (currNode.next != null && currNode.next.element != item) {
        // 把记录节点的位置向下链式移动一位
        currNode = currNode.next;
      }
      return currNode; // 返回找到的节点
    }
    // 找到指定链表中的元素位置
    find(item) {
      let currNode = this.head; // 记录当前节点位置，默认在头部处
      // 当前节点不等于 查找的item节点的时候，一直循环
      while (currNode.element != item) {
        // 把记录节点的位置向下链式移动一位
        currNode = currNode.next;
      }
      return currNode; // 返回找到的节点
    }
    // 插入元素到指定链表中
    insert(newElement, item) {
      let newNode = new Node(newElement); // 创建新的节点
      let currNode = this.find(item); // 找到插入节点的位置，简称A节点
      // 把新创建的节点后继，指向你要插入某个节点的后继（A节点后继）
      newNode.next = currNode.next;
      // 并且把你指定A节点后继 指向 刚刚创建的新节点
      currNode.next = newNode;
      // 就是断了A节点后继线，让新的关联起来，并且让A后继关联到新节点去。
    }
    // 删除链表节点方法
    remove(item) {
      let preNode = this.findPreivious(item); // 找到删除节点的前驱
      let currNode = this.find(item); // 找到删除节点的后继
      // 不是结尾的节点都可以处理
      if (preNode.next != null) {
        // 前驱节点指向 删除节点指向的后继
        preNode.next = currNode.next;
        // 清空删除节点的后继指向--因为要删除了，并且只能有一个后继
        currNode.next = null;
        currNode = null; // 删除变量,等待回收
      }
    }
    // 辅助方法-遍历,测试结果
    traverse() {
      let currNode = this.head; // 从头节点开始遍历
      // 只要不为空就一直遍历，结尾指向的就是Null
      while (currNode.next != null) {
        console.log(currNode.next.element);
        // 在把当前节点指向后一个
        currNode = currNode.next;
      }
    }
  }

  let cities = new LinkedList(); // 创建链表
  // 第一个参数：插入的新值，第二参数：插入在已有节点上（必须有的）
  // 把first插入到head节点后面
  cities.insert('first', 'head');
  cities.insert('second', 'first');
  cities.insert('thrid', 'second');
  cities.insert('two', 'thrid');
  // 在把heheh插入到 second节点入，上面有指定插入此节点的，查看是否插入正确
  cities.inser;
}

{
  // 反转链表

  // 法一
  // 借助栈 将链表的值存放到数组，反转数组，然后在重新赋值（但是这么没有用到链表的特性）

  function reverseList(head) {
    if (!head) return null;
    let temp = head;
    let result = [];
    while (temp !== null) {
      result.push(temp.val);
      temp = temp.next;
    }

    temp = head;
    let i = 0;
    result.reverse();
    while (temp !== null) {
      temp.val = result[i];
      i++;
      temp = temp.next;
    }

    return head;
  }

  // 法二
  // 局部反转构成整体反转 (原地反转)
  // 1 2 3 4
  // 2 1 3 4
  // 3 2 1 4
  // 4 3 2 1

  // 1 2 3 4 5
  // 2 1 3 4 5
  // 3 2 1 4 5
  // 4 3 2 1 5
  // 5 4 3 2 1

  // 解决思路
  // 1 遍历链表时，将当前节点的next指向改为指向前一个元素
  // 2 由于节点没有引用其上一个节点，因此必须实现存储其前一个元素
  // 3 在更改应用之前，还需要另一个指针来村存储下下一个节点
  // 4 不要忘记在最后返回新的头引用

  function reverseList(head) {
    if (!head) return null;

    let prev = null; // 创建这个变量作为反转链表的尾部
    let curr = head; // 这个变量用于不断的移动指针
    // a(next) -> b(next) -> c(next) -> null
    // =>
    // null <- (next)c <- (next)b <- (next)a
    while (curr) {
      let next = curr.next; // 翻转之前需要先保存next节点，不然翻转之后找不到这个位置的元素了
      curr.next = prev; // 当前节点next指针翻转指向pre前置节点
      prev = curr; // 将prev 移动到 curr当前的位置
      curr = next; // 将curr 移动到 next的位置 执行下一次的循环
    }

    // 退出while循环的条件是 curr 为 null。只要明白一件事情
    // pre 指向的是curr的前一个元素。所以翻转之后返回的应该是prev
    return prev;
  }

  // 法三 尾递归
  // 其实就是解法二的简化版
  // prev = curr;
  // curr = next;
  function reverseList(head) {
    let reverse = (prev, curr) => {
      if (!curr) return prev;
      let next = curr.next;
      curr.next = prev;

      return reverse(curr, next);
    };

    return reverse(null, head);
  }
}

{
  // 输入一个链表，反转链表后，输出链表的表头

  // 参考答案
  // 法1 借助栈
  // 借助栈的后进先出，可以将顺序列表逆序。不过这不是原地反转，当然题目也没有要求
  // 处理过程如下：
  // 从头到尾遍历链表，将节点的 val 依次放入栈
  // 从栈中依次取出 val 构造新节点，并连接节点
  // 时间复杂度O(n)，空间复杂度O(n)

  function reverseList(head) {
    if (!head) {
      return null;
    }

    const stack = [];
    let node = head;
    while (node) {
      stack.push(node.val);
      node = node.next;
    }

    const newHead = {
      val: stack.pop(),
      next: null,
    };

    node = newHead;
    while (stack.length) {
      node.next = {
        val: stack.pop(),
        next: null,
      };
      node = node.next;
    }

    return newHead;
  }

  // 法2 原地反转
  // 原地反转的思路简单，但是实现起来有一些细节需要处理。链表类的原地操作，大部分都是细节上容易出错，导致死循环或者报错

  // 准备当前节点node和node的前一个节点preNode，整体思路如下：
  // 保留当前节点的下一个节点
  // 将当前节点的next指向前一节点preNode
  // 更新preNode为当前节点，更新当前节点为第一步保留的下一节点
  // 判断当前节点是否是最后节点，如果不是，回到第一步；如果是，进入最后一步
  // 将当前节点的next指向前一节点 preNode
  // 时间复杂度O(n)，空间复杂度O(1)

  function reverseList(head) {
    if (!head) {
      return null;
    }

    let node = head;
    let preNode = null;
    while (node.next) {
      const nextNode = node.next;
      node.next = preNode;
      preNode = node;
      node = nextNode;
    }
    node.text = preNode;

    return node;
  }
}

{
  // 输入一个链表，输出该链表中倒数第k个节点

  // 参考答案
  // 解法1 两次循环
  // 因为要求链表倒数第k个节点，也就是正数第length - k个节点。整体流程如下：
  // 链表又是单个链表，并且没有保存长度信息。所以需要循环一次计算length
  // 第二次循环找到第length - k个节点
  // 时间复杂度是O(n)，需要2次循环

  function getKthFromHead(head, k) {
    let length = 0;
    let node = head;
    while (node) {
      ++length;
      node = node.next;
    }

    if (k > length) {
      return null;
    }

    node = head;
    let offSet = length - k;
    for (let i = 0; i < offSet; i++) {
      node = node.next;
    }

    return node;
  }

  // 解法2 快慢双指针
  // 准备两个指针：left（慢）right（快），整体过程如下
  // right 先向右移动 k 位，此时 index(right) - index(left) = k
  // left 和 right 一起向右移动，直到 right 到达边界
  // 由于 index(right) - index(left) = k，所以
  // index(left) = index(right) - k = lenght - k
  // 也就是 left 指针移动到了倒数第k个位置
  // 时间复杂度是O(n)，但是仅需遍历一次。空间复杂度是O(1)

  function getKthFromHead(head, k) {
    let right = head;
    for (let i = 0; i < k; i++) {
      if (right === null) {
        // 链表长度小于k
        return null;
      }
      right = right.next;
    }

    let left = head;
    while (right) {
      left = left.next;
      right = right.next;
    }

    return left;
  }
}

{
  // 请判断一个链表是否为回文链表;
  //  示例 1:
  // 输入: 1->2
  // 输出: false
  // 示例 2:
  // 输入: 1->2->2->1
  // 输出: true
  // 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  // 法一
  // 利用前后累加字符串对比
  var isPalindrome = function (head) {
    let a = '';
    let b = '';
    while (head !== null) {
      a = a + head.val;
      b = head.val + b;
      head = head.next;
    }

    return a === b;
  };

  // 法二
  // 快慢指针
  var isPalindrome = function (head) {
    let low = head;
    let fast = head;
    if (!head || !head.next) {
      return true;
    }
    const values = [];
    // 通过快慢指针找到链表的中点
    while (fast && fast.next) {
      values.push(low.val);
      fast = fast.next.next;
      low = low.next;
    }
    // 处理链表长度只有 1 的情况
    if (!values.length) {
      return true;
    }
    // 处理奇偶链表的差异
    if (fast) {
      low = low.next;
    }
    // 通过比较后半段链表的值和前半段链表的值是否相等从而判断是否为回文链表
    while (low) {
      let curVal = values.pop();
      if (curVal !== low.val) {
        return false;
      }
      low = low.next;
    }
    return true;
  };

  // 法三
  // 通过 快、慢指针找链表中点，然后反转链表，比较两个链表两侧是否相等，来判断是否是回文链表
  var isPalindrome = function (head) {
    let left = head;
    let right = reverse(head);

    while (right !== null) {
      if (left.val !== right.val) {
        return false;
      }
      left = left.next;
      right = right.next;
    }

    return true;
  };

  function reverse(head) {
    let prev = null;
    let curr = head;
    while (curr) {
      let next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

  function findCenter(head) {
    let slower = head;
    let faster = head;
    while (faster && faster.next) {
      faster = faster.next.next;
      slower = slower.next;
    }

    // 如果 faster 不等于 null，说明是奇数个，slower 再移动一格
    if (faster !== null) {
      slower = slower.next;
    }

    return slower;
  }
}

{
  // 环形链表
  // 给定一个链表，判断链表中是否有环。
  // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
  // 进阶：你能用 O(1)（即，常量）内存解决此问题吗？

  // 法一 利用数组判断
  const hasCycle = function (head) {
    const res = [];
    while (head) {
      if (res.includes[head]) {
        return true;
      }
      res.push(head);
      head = head.next;
    }
    return false;
  };

  // 法二 快慢指针
  const hasCycle = function (head) {
    if (head === null || head.next === null) {
      return false;
    }

    let slower = head;
    let faster = head.next;
    while (slower) {
      if (slower === faster) {
        return true;
      }
      slower = slower.next;
      faster = faster.next.next;
    }
    return false;
  };

  // 法三 污染链表法
  const hasCycle = function (head) {
    while (head) {
      if (head.flag === true) {
        return true;
      }
      head.flag = true;
      head = head.next;
    }
    return false;
  };

  // 法四 JSON.stringify方法会自动检测传入的对象是否为环
  const hasCycle = function (head) {
    try {
      JSON.stringify(head);
      return false;
    } catch (error) {
      return true;
    }
  };
}

{
  // 相交链表
  // 编写一个程序，找到两个单链表相交的起始节点。

  // 法一 暴力发
  var getIntersectionNode = function (headA, headB) {
    let tempA = headA;
    while (tempA) {
      let tempB = headB;
      while (tempB) {
        if (tempA === tempA) {
          return tempA;
        }
        tempB = tempB.next;
      }
      tempA = tempA.next;
    }
  };

  // 法二 哈希表
  var getIntersectionNode = function (headA, headB) {
    let tempA = headA;
    let tempB = headB;
    let map = new Map();
    while (tempA) {
      map.set(tempA, 1);
      tempA = tempA.next;
    }

    while (tempB) {
      if (map.get(tempB)) {
        return tempB;
      }
      tempB = tempB.next;
    }
  };

  // 法三 双指针
  // 1 使用两个指针pA，pB 分别从A B来个那个链表头部开始遍历，步长为一
  // 2 当一个指针遍历到尾部时，将它移动到另一个链表的头部重新开始遍历
  // 3 如果两个链表有交点的话，pA和pB一定会相遇
  // 如果链表有交点：
  // 1）两个链表长度一样，第一次遍历就能找到交点
  // 2）两个链表长度不一样，第二次遍历能找到节点
  // 如果链表没有交点
  // 1）两个链表长度一样，第一次遍历后pA pB都是null，结束遍历
  // 2）两个链表长度不一样，两次遍历结束后pA pB都是null，结束遍历

  // 时间复杂度：O(M + N)O(M+N), M, N 分别为两个链表的长度。
  // 空间复杂度：O(1)O(1)。

  var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) {
      return null;
    }

    let tempA = headA;
    let tempB = headB;
    while (tempA !== tempB) {
      tempA = tempA === null ? tempB : tempA.next;
      tempB = tempB === null ? tempA : tempB.next;
    }
    return tempA;
  };
}
